---
title: "3、数列求值"
created: 2025-11-28
tags:
  - 算法
---

# 3、数列求值

## 题目 [数列求值](https://www.lanqiao.cn/paper/3842/problem/600/)

![[image-0862e1de.png]]

## 思路分析

简单dp（斐波那契）

注意溢出问题 开long long每轮模上10000

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=2e8+10;

LL f[N];

int main()

{

	f[1]=f[2]=f[3]=1;

	for(LL i=4;i<=20200000;i++){

		f[i]=(f[i-1]+f[i-2]+f[i-3])%10000;

		cout<<f[i]<<" ";

	}

	cout<<f[20190324]%10000;

	return 0;

 }
```

可以用变量滚动优化 但是怕出错

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int main()

{

    LL a=1, b=1, c=1, next;

    for(LL i=4; i<=20190324; ++i){

        next = (a + b + c) % 10000;

        a = b;

        b = c;

        c = next;

    }

    cout << c;

    return 0;

}
```

如果还是担心越界出错的问题 这种简单填空题可以用py写一下

![[image-f507c2ea.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int main()

{

    LL a=1, b=1, c=1, next;

    for(LL i=4; i<=20190324; ++i){

        next = (a + b + c) % 10000;

        a = b;

        b = c;

        c = next;

    }

    cout << c;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2、年号字串|2、年号字串]] 🏠 [[00-刷题理模型]] ➡️ [[4、数的分解|4、数的分解]]